﻿//We are given an array of integers and a number S.
//Write a program to find if there exists a subset of the elements of the array that has a sum S.
//Example: arr={2, 1, 2, 4, 3, 5, 2, 6}, S=14 -> yes (1+2+5+6)


using System;
using System.Collections.Generic;

public class SubsetOfElementsEqualToGivenSum
{
    public static void Main()
    {
        Console.Write("Enter sum S = ");
        int sum = int.Parse(Console.ReadLine());
        Console.Write("Enter number n = ");
        int count = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} numbers", count);
        int[] numbers = new int[count];
        for (int i = 0; i < count; i++)
        {
            numbers[i] = int.Parse(Console.ReadLine());
        }
        Console.WriteLine();

        int zeroSumCount = 0;
        for (int combinationCount = 1; combinationCount < Math.Pow(2, count); combinationCount++)
        {
            int tempSum = 0;
            List<int> combination = new List<int>();
            combination = GetCombination(combinationCount);

            for (int j = 0; j < combination.Count; j++)
            {
                tempSum += numbers[combination[j]];
            }
            if (sum == tempSum)
            {
                zeroSumCount++;
                Console.Write('{');
                for (int k = 0; k < combination.Count; k++)
                {
                    if (k < combination.Count - 1)
                    {
                        Console.Write("{0}, ", numbers[combination[k]]);
                    }
                    else
                    {
                        Console.Write("{0}", numbers[combination[k]]);
                    }

                }
                Console.Write("}\n");
            }
        }

        Console.WriteLine("The number of combinations are {0}", zeroSumCount);
    }

    private static List<int> GetCombination(int count)
    {
        string binaryLength = Convert.ToString(count, 2);
        List<int> combination = new List<int>();
        for (int i = 0; i < binaryLength.Length; i++)
        {
            int mask = 1;
            if ((count & mask) == 1)
            {
                combination.Add(i);
            }
            count >>= 1;
        }

        return combination;
    }
}